◀ Prev · Parts · Full · Next ▶

One of the earliest randomized data structures is the hash table, which was introduced in 1953 by Hans Peter Luhn at IBM.cite-ref-0-9-0[9] Luhn's hash table used chaining to resolve collisions and was also one of the first applications of linked lists.cite-ref-0-9-1[9] Subsequently, in 1954, Gene Amdahl, Elaine M. McGraw, Nathaniel Rochester, and Arthur Samuel of IBM Research introduced linear probing,cite-ref-0-9-2[9] although Andrey Ershov independently had the same idea in 1957.cite-ref-0-9-3[9] In 1962, Donald Knuth performed the first correct analysis of linear probing,cite-ref-0-9-4[9] although the memorandum containing his analysis was not published until much later.cite-ref-10[10] The first published analysis was due to Konheim and Weiss in 1966.cite-ref-11[11]

◀ Prev · Parts · Full · Next ▶